package leetcode101.dynamic_planning;

/**
 * @author Synhard
 * @version 1.0
 * @Class Code12
 * @Description 0-1背包问题
 * 有 N 个物品和容量为 W 的背包，每个物品都有
 * 自己的体积 w 和价值 v，求拿哪些物品可以使得背包所装下物品的总价值最大。
 *
 * 求当前背包最多能装多大重量的物品
 * 示例1
 * 输入
 * 10,2,[[1,3],[10,4]]
 * 返回值
 * 4
 * 说明
 * 第一个物品的体积为1，重量为3，第二个物品的体积为10，重量为4。只取第二个物品可以达到最优方案，取物重量为4
 * @tel 13001321080
 * @email 823436512@qq.com
 * @date 2021-04-15 8:39
 */
public class Code12 {
    public static void main(String[] args) {
        int volume = 10;
        int[][] goods = new int[][]{{1, 3}, {10, 4}};
        System.out.println(knapsackTwoDim(volume, goods));
    }

    /*
    0-1背包的二维dp矩阵解法
     */
    public static int knapsackTwoDim (int volume, int[][] goods) {
        int number = goods.length;
        int[][] dp = new int[number + 1][volume + 1]; // 声明dp数组辅助求解
        int m = dp.length;
        int n = dp[0].length;

        /*
        为行赋初值
         */
        for (int i = 1; i < m; i++) {
            if (goods[i - 1][0] <= 1) {
                dp[i][1] = goods[i - 1][1];
            }
        }

        /*
        为列赋初值
         */
        for (int i = 1; i < n; i++) {
            if (goods[0][0] <= i) {
                dp[1][i] = goods[0][1];
            }
        }

        /*
        填dp数组
         */
        for (int i = 2; i < m; i++) { // i 代表物品编号
            for (int j = 2; j < n; j++) { // j 代表了当前的体积
                if (j >= goods[i - 1][0]) {
                    dp[i][j] = Math.max(dp[i - 1][j], dp[i - 1][j - goods[i - 1][0]] + goods[i - 1][1]);
//                    dp[i][j] = Math.max(dp[i - 1][j], dp[i - 1][j - goods[i][0]] + goods[i - 1][1]);
                } else {
                    dp[i][j] = dp[i - 1][j];
                }
            }
        }

        return dp[m - 1][n - 1];
    }

    /*
    0-1背包的一维矩阵解法
     */

}
/*
可以使用动态规划解决背包问题，首先是0-1背包
定义dp数组存储最大价值，其中dp[i][j]表示前i件物品再体积不超过j的情况下能达到的最大价值
在我们遍历到第i件物品时，在当前背包总容量为j的情况下，
如果我们不把物品i放入背包，dp[i][j] = dp[i - 1][j]即前i个物品的最大价值等于只取前i - 1个物品时的最大价值。
如果我们将物品i放入背包的话假设第i件物品体积为w，价值为v，那么我们得到dp[i][j] = dp[i - 1][j - w] + v
综上dp[i][j] = Max{dp[i - 1][j], dp[i - 1][j - w] + v}
对于完全背包一个物品可以拿多次，
假设我们遍历到物品 i = 2，
且其体积为 w = 2，价值为 v = 3；对于背包容量 j = 5，最多只能装下 2 个该物品。那么我们的状
态转移方程就变成了 dp[2][5] = Max{dp[1][5], dp[1][3] + 3, dp[1][1] + 6}。如果采用这种方法，假设
背包容量无穷大而物体的体积无穷小，我们这里的比较次数也会趋近于无穷大，远超 O(NW) 的
时间复杂度。
怎么解决这个问题呢？我们发现在 dp[2][3] 的时候我们其实已经考虑了 dp[1][3] 和 dp[1][1]的情况，
即dp[2][3] = Max{dp[1][3], dp[1][1] + 3}因此，对于拿多个物品的情况，
我们只需考虑 dp[2][3] 即可，即 dp[2][5] = Max{dp[1][5], dp[2][3] + 3}。这样，我们
就得到了完全背包问题的状态转移方程：dp[i][j] = max(dp[i-1][j], dp[i][j-w] + v)，其与 0-1 背包问
题的差别仅仅是把状态转移方程中的第二个 i-1 变成了 i。
 */